18. 四数之和
18. 四数之和
分析
这个题跟 1. 两数之和、15. 三数之和 才是一样的，跟 454. 四数相加 II 反而没什么关系
一开始的时候，我想参考 454. 四数相加 II 的写法，先通过记录数组中所有的两个组合的和，然后遍历这些和，同时在 HashMap 中查找 target-当前和
，来将四个指针的问题降维为两个指针的问题（还是 Hash 表），但是发现在去重问题上翻了车，始终无法实现输入 [2,2,2,2,2] 输出 [[2,2,2,2]]，因为我没有记录和出现的次数，而是去重了。
感觉思路又错了，最后看官方题解，居然在 15. 三数之和 的基础上再套一层 for 循环即：是三层 for 循环嵌套 + 双指针。
15. 三数之和 的双指针解法是一层 for 循环 num[i] 为确定值，然后循环内有 left 和 right 下标作为双指针，找到 nums[i] + nums[left] + nums[right] == 0。
四数之和的双指针解法是两层 for 循环 nums[a] + nums[b] 为确定值，依然是循环内有 left 和 right 下标作为双指针，找出 nums[a] + nums[b] + nums[left] + nums[right] == target 的情况，三数之和的时间复杂度是
而且如果有五数之和、六数之和之类的题，也都是这类写法，好吧，挺无聊的。
此外，注意看本体的提示部分
-109 <= nums[i] <= 109-109 <= target <= 109
int 类型最大值是 20 多亿，也就是，而单个元素最大就可能有 ，也就是说四个元素的和有可能超过 int 的最大值，因此需要用 long 类型来保存四个元素得和，这应该是这个题最大的难点了，哈哈哈
此外，代码随想录 中还提到了各层循环的剪枝操作，这里就懒得记了。
解题
public List<List<Integer>> fourSum(int[] nums, int target) {
List<List<Integer>> result = new ArrayList<>();
// 必须要先排序
Arrays.sort(nums);
for(int a=0;a<nums.length;a++){
if(a>0&&nums[a]==nums[a-1]){
continue;
}
// 第二层循环从第一个指针的下一个元素开始
for(int b=a+1;b<nums.length;b++){
if(b>a+1&&nums[b]==nums[b-1]){
continue;
}
int left = b+1,right=nums.length-1;
while(left<right){
long sum = (long)nums[a]+(long)nums[b]+(long)nums[left]+(long)nums[right];
if(sum<target){
left++;
}else if(sum>target){
right--;
}else{
List<Integer> pairs = new ArrayList<>();
pairs.add(nums[a]);
pairs.add(nums[b]);
pairs.add(nums[left]);
pairs.add(nums[right]);
result.add(pairs);
while( left+1<right && nums[left]==nums[left+1]){
left++;
}
while( left<right-1 && nums[right]==nums[right-1]){
right--;
}
left++;
right--;
}
}
}
}
return result;
}